package com.imooc.distributedemo.resume.leetcode;

import cn.hutool.core.collection.CollUtil;
import org.springframework.util.CollectionUtils;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.ThreadPoolExecutor;

/**
 * leetcode41 缺失的第一个正数
 */
public class Solution41 {
    public static void main(String[] args) {
        int[] nums1={3,4,-1,1};
        int[] nums2={7,8,9,11,12};

        int r1 = firstMissingPositive(nums1);
        int r2 = firstMissingPositive(nums2);
        System.out.println(r1);
        System.out.println(r2);
    }

    public static int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) {
                // 下标+1=当前值  就不缺
                return i + 1;
            }
        }
//        new ThreadPoolExecutor();
        return n + 1;
        /*if(null==nums||nums.length<1){
            return -1;
        }
        List<Integer> tmp=new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]>0){
                tmp.add(nums[i]);
            }
        }
        Collections.sort(tmp);
        int tmpMaxNum = tmp.get(tmp.size()-1);
        List<Integer> originData = new ArrayList<>();
        List<Integer> newData = new ArrayList<>();
        for (int i = 1; i < tmpMaxNum+1; i++) {
            if(tmp.contains(i)){
                originData.add(i);
            }else{
                originData.add(0);
            }
            newData.add(i);
        }
        for (int i = 0; i < originData.size(); i++) {
            if(originData.get(i)*newData.get(i)==0){
                return newData.get(i);
            }
        }*/

        /*List<Integer> tmp=new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]>0){
                tmp.add(nums[i]);
            }
        }
        Collections.sort(tmp);
        int tmpMaxNum = tmp.get(tmp.size()-1);
        // 对空间复杂度没有要求的情况
        List<Integer> copyList = new ArrayList<>();
        for (int i = 1; i < tmpMaxNum+1; i++) {
            copyList.add(i);
        }
        // 取2个集合的差集的最小值
        Collections.sort(copyList);
        List<Integer> diffList = (List<Integer>)CollUtil.disjunction(tmp,copyList);
        if(CollectionUtils.isEmpty(diffList)){
            return -1;
        }
        int result = diffList.get(0);*/
//        return -1;
    }
}
